package com.learn.algorithm_108;

import com.dataconsruct.TreeNode;
import com.dataconsruct.TreeOperation;

/**
 * 将有序数组转换为高度平衡二叉搜索树
 * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
 */
public class ArrayToTreeNode {

    public static void main(String[] args) {
        int[] arr = {-10, -9, -7, -5, -3, 1, 2, 3, 5, 9, 11};
        TreeNode root = new ArrayToTreeNode().sortedArrayToBST(arr);
        TreeOperation.show(root);
    }

    private TreeNode sortedArrayToBST(int[] arr) {
        if (arr == null) {
            return null;
        }
        return rootNode(arr, 0, arr.length - 1);
    }

    private TreeNode rootNode(int[] arr, int left, int right) {
        if (left > right || left < 0) {
            return null;
        }
        // 中间位置，按index计算
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(arr[mid]);
        root.left = rootNode(arr, left, mid - 1);
        root.right = rootNode(arr, mid + 1, right);
        return root;
    }

}
